#! /usr/bin/python

import math
import time
tt = time.time()
limit = 10**5


def sieve(n):
    phi = [i for i in range(limit)]
    for i in range(2, int(math.sqrt(n) + 1)):
	   for j in range(i**2, n, i):
	       phi[j] = 0
    return [p for p in phi if p != 0]

primes = sieve(limit)
#print phi
primes.remove(1)

#print primes.count(221)

phi = [i for i in range(limit)]

for i in range(2, len(phi)):
    if phi[i] == i:
	for j in range(i, len(phi), i):
	    phi[j] = phi[j]/i*(i-1)

maxi = 0
flag = 0

base = 2*3*5*7*11
phii = 2*4*6*10
print primes[5]
for i in range(5, len(primes)):
    base *= primes[i]
    phii *= (primes[i] - 1)
    ratio = (base-1)/float(phii)
    if ratio > float(94744)/15499:
        print base, i, ratio
        #print base, i, ratio, (base/29 - 1)/float(phii/28), base/29
	break
    print base, i, ratio, (4*base-1)/(4*float(phii)), 4*base

print primes[0:10]
print time.time() - tt

